STL"源码"剖析

2023-06-30 12:28| 来源: 网络整理| 查看: 265

　　STL是C++重要的组件之一，大学时看过《STL源码剖析》这本书，这几天复习了一下，总结出以下LZ认为比较重要的知识点，内容有点略多 :)

1、STL概述

STL提供六大组件，彼此可以组合套用：

容器（Containers）：各种数据结构，如：vector、list、deque、set、map。用来存放数据。从实现的角度来看，STL容器是一种class template。算法（algorithms）：各种常用算法，如：sort、search、copy、erase。从实现的角度来看，STL算法是一种 function template。迭代器（iterators）：容器与算法之间的胶合剂，是所谓的“泛型指针”。共有五种类型，以及其他衍生变化。从实现的角度来看，迭代器是一种将 operator*、operator->、operator++、operator- - 等指针相关操作进行重载的class template。所有STL容器都有自己专属的迭代器，只有容器本身才知道如何遍历自己的元素。原生指针(native pointer)也是一种迭代器。仿函数（functors）：行为类似函数，可作为算法的某种策略（policy）。从实现的角度来看，仿函数是一种重载了operator()的class或class template。一般的函数指针也可视为狭义的仿函数。配接器（adapters）：一种用来修饰容器、仿函数、迭代器接口的东西。例如：STL提供的queue 和 stack，虽然看似容器，但其实只能算是一种容器配接器，因为它们的底部完全借助deque，所有操作都由底层的deque供应。改变 functors接口者，称为function adapter；改变 container 接口者，称为container adapter；改变iterator接口者，称为iterator adapter。配置器（allocators）：负责空间配置与管理。从实现的角度来看，配置器是一个实现了动态空间配置、空间管理、空间释放的class template。

STL六大组件的交互关系

一些可能令人困惑的C++语法糖：

静态常量整数成员(double就不行)在class内部直接初始化静态成员只能在类外初始化，且初始化时不加static 基类够构造函数中调用virtual函数实际调用的是基类中的virtual函数(这点和Java不同) 任何一个STL算法，都需要获得有一对迭代器(泛型指针)所指示的区间用以表示操作的范围。这一对迭代器表示的就是前闭后开区间

泛型指针、原生指针和智能指针泛型指针有多种含义。指void*指针，可以指向任意数据类型，因此具有“泛型”含义。指具有指针特性的泛型数据结构，包含泛型的迭代器、智能指针等。广义的迭代器是一种不透明指针，能够实现遍历访问操作。通常所说的迭代器是指狭义的迭代器，即基于C++的STL中基于泛型的iterator_traits实现的类的实例。总体来说，泛型指针和迭代器是两个不同的概念，其中的交集则是通常提到的迭代器类。原生指针就是普通指针，与它相对的是使用起来行为上像指针，但却不是指针。说“原生”是指“最简朴最基本的那一种”。因为现在很多东西都抽象化理论化了，所以“以前的那种最简朴最基本的指针”只是一个抽象概念（比如iterator）的表现形式之一。智能指针是C++里面的概念：由于 C++ 语言没有自动内存回收机制，程序员每次得自己处理内存相关问题，但用智能指针便可以有效缓解这类问题。引入智能指针可以防止出现悬垂指针的情况，一般是把指针封装到一个称之为智能指针类中，这个类中另外还封装了一个使用计数器，对指针的复制等操作将导致该计数器的值加1，对指针的delete操作则会减1，值为0时，指针为NULL

2、迭代器

　　STL的中心思想是：将数据容器和算法分隔开，彼此独立设计，最后再用黏合剂将它们撮合在一起。容器和算法的泛型化，可以用C++的class template和function template来实现，而二者的黏合剂就是迭代器了。

迭代器是一种智能指针

　　与其说迭代器是一种指针，不如说迭代器是一种智能指针，它将指针进行了一层封装，既包含了原生指针的灵活和强大，也加上很多重要的特性，使其能发挥更大的作用以及能更好的使用。迭代器对指针的一些基本操作如*、->、++、==、!=、=进行了重载，使其具有了遍历复杂数据结构的能力，其遍历机制取决于所遍历的数据结构。下面上一段代码，了解一下迭代器的“智能”：

template class Iterator { public: Iterator& operator++(); //... private: T *m_ptr; };

　　对于不同的数据容器，以上Iterator类中的成员函数operator++的实现会各不相同，例如，对于数组的可能实现如下：

//对于数组的实现 template Iterator& operator++() { ++m_ptr; retrun *this; }

　　对于链表，它会有一个类似于next的成员函数用于获取下一个结点，其可能实现如下：

//对于链表的实现 template Iterator& operator++() { m_ptr = m_ptr->next();//next()用于获取链表的下一个节点 return *this; }

　　iterator首先要对iterator指向对象的实现细节有非常丰富的了解，所以iterator为了不暴露所指向对象的信息，干脆就将iterator的实现由各个容器的设计者来实现好了。STL将迭代器的实现交给了容器，每种容器都会以嵌套的方式在内部定义专属的迭代器。各种迭代器的接口相同，内部实现却不相同，这也直接体现了泛型编程的概念。

迭代器使用示例 #include #include #include #include using namespace std; int main(int argc, const char *argv[]) { int arr[5] = { 1, 2, 3, 4, 5 }; vector iVec(arr, arr + 5);//定义容器vector list iList(arr, arr + 5);//定义容器list //在容器iVec的头部和尾部之间寻找整形数3 vector::iterator iter1 = find(iVec.begin(), iVec.end(), 3); if (iter1 == iVec.end()) cout

【本文地址】

公司简介

联系我们